import functools


class Solution(object):
    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        n = len(graph)

        @functools.cache
        def search(u):
            if u == n - 1:
                return [[u]]
            out = []
            for v in graph[u]:
                next_out = search(v)
                for one_out in next_out:
                    out.append([u] + one_out)
            return out

        return search(0)


data = Solution()
gragh = [[1, 2], [3], [3], []]
print(data.allPathsSourceTarget(gragh))
